import org.junit.Test;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * 手动实现一个选择排序算法：并测算处理80000个排序，需要花费多少时间?  本人电脑：2秒
 */
public class SelectSortDemo {
    public static void main(String[] args) {
        int[] ints = new int[]{3,9,-1,10,20};
        System.out.println("排序前数组：");
        System.out.println(Arrays.toString(ints));
        selectSort(ints);
        System.out.println("排序后数组：");
        System.out.println(Arrays.toString(ints));
        System.out.println("---------------------------");

        //测试选择排序的时间复杂度
        //若处理80000个排序，需要花费多少时间? 本人电脑花费2秒
        selectSortTest();

    }

    //测试选择排序的时间复杂度
    //测试算法：若处理80000个排序，需要花费多少时间? 本人电脑花费2秒
    public static void selectSortTest(){
        int[] arr = new int[80000];
        //先随机生成一个容量为80000个的数组
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random()*80000);
        }
        //创建 格式化日期格式对象：
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy.MM.dd HH:mm:ss");
        //创建当前时间的对象
        Date time1 = new Date();
        //对当前时间进行格式化
        String s1 = sdf.format(time1);
        //打印
        System.out.println("排序前时间："+s1);
        //进行排序
        selectSort(arr);
        //再次创建当前时间对象
        Date time2 = new Date();
        String s2 = sdf.format(time2);
        System.out.println("排序后时间："+s2);
    }

    //选择排序算法
    public static void selectSort(int[] arr){
        //1.先确定总共需要进行多少次选择排序,并进行循环
        for (int i = 0; i < arr.length-1; i++) {
            //假定数组第一个值为最小值,后面逐渐依次假定
            int min = arr[i];
            //假定最小值下标为：0,后面逐渐依次假定
            int minIndex = i;
            //2.再进行每一次选择排序循环
            //注意:每次循环完次数要减一,且不是从头开始
            for (int j = 0+i; j < arr.length-1; j++) {
                //若数组中存在一个数比假定值小，则假定值获得该最小值，并记录最小值下标。直到循环结束，再将最小值与arr[0]交换位置
                if (arr[j] < min) {
                    min = arr[j];
                    minIndex = j;
                }
            }
            //3.交换每次循环出来的最小值,将最小值与数组第一位数进行交换，第二小值与数组第二位数交换，依次类推
            if (minIndex != i) {//若假定值就是最小值，就不用交换了
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
    }
}
